'''
@Author: shj
@Date: 2020-06-02 10:54:03
@LastEditTime: 2020-06-02 11:24:59
@LastEditors: shj
@Description:  链表中倒数第k个结点
@FilePath: /python3/algorithms/offer_code/14_the_last_K_node_in_list.py
'''
'''
题目描述
输入一个链表，输出该链表中倒数第k个结点。

思路
法1 计算出总长度count，然后正向输出count - k位的节点（起始位为0）

法2 快慢指针（fast - slow = k）
初始快慢指针在同一位，快指针先走k位，然后慢指针再走，当快指针指向节点为空时，慢指针所指节点即为所求
'''
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        # 空链表或定位指针越界处理
        if head is None or k < 1:
            return None
        # 快、慢指针,快指针先走k步，然后快慢指针同步走
        (fast, slow) = (head, head)
        while k:  # fast先行步数为0时停止
            # 若k超过链表长度，返回None
            if fast:
                fast = fast.next
                k -= 1
            else:
                return None
        # 快慢指针同步走
        while fast:  # 当fast为None时停止
            fast = fast.next
            slow = slow.next
        return slow
